package com.demo.java.OD51_100.OD73;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【流水线】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145619648
 */
public class OdMain {
    public static void main(String[] args) {
        try {
            // 创建 Scanner 对象用于读取输入
            Scanner s = new Scanner(System.in);

            // 读取机器数量和任务数量，并按空格分割
            String[] strs = s.nextLine().split(" ");
            // 读取每个任务的持续时间，并按空格分割
            String[] jobs = s.nextLine().split(" ");

            // 调用 solve 方法来解决问题
            solve(strs, jobs);
        } catch (Exception e) {
            // 捕获异常并打印错误信息
            e.printStackTrace();
            System.out.println("input error");
        }
    }

    public static void solve(String[] strs, String[] jobs) {
        // 从输入获取机器的数量和任务的数量
        int m = Integer.parseInt(strs[0]);  // m 为机器的数量
        int n = Integer.parseInt(strs[1]);  // n 为任务的数量

        // 创建一个数组来存储每个任务的持续时间
        int[] jobDurations = new int[n];
        for (int i = 0; i < n; i++) {
            jobDurations[i] = Integer.parseInt(jobs[i]);  // 将每个任务的持续时间转换为整数并存储
        }

        // 将任务的持续时间按升序排序
        Arrays.sort(jobDurations);

        // 使用最小堆 (Min-heap) 来跟踪每台机器的工作负载
        PriorityQueue<Integer> machineWorkloads = new PriorityQueue<>();

        // 初始化堆，将每台机器的初始工作负载设置为 0
        for (int i = 0; i < m; i++) {
            machineWorkloads.add(0);
        }

        // 分配任务
        for (int job : jobDurations) {
            // 弹出当前工作负载最小的机器（即最空闲的机器）
            int leastWorkload = machineWorkloads.poll();
            // 将当前任务的持续时间添加到该机器的工作负载
            machineWorkloads.add(leastWorkload + job);
        }

        // 最终结果是所有机器中的最大工作负载
        int result = Collections.max(machineWorkloads);  // 获取最重的机器的工作负载
        System.out.println(result);  // 输出结果
    }
}